Proof of a conjecture of Frankl and Furedi

摘要

We give a simple linear algebraic proof of the following conjecture of Frankl and Furedi [7, 9, 13].\ud(Frankl-Furedi Conjecture) if F is a hypergraph on X = {1, 2, 3,..., n} such that\ud1 less than or equal to /E boolean AND F/ less than or equal to k For All E, F is an element of F, E not equal F,\udthen /F/ less than or equal to (i=0)Sigma(k) ((i) (n-1)).\udWe generalise a method of Palisse and our proof-technique can be viewed as a variant of the technique used by Tverberg to prove a result of Graham and Pollak [10, 11, 14]. Our proof-technique is easily described. First, we derive an identity satisfied by a hypergraph F using its intersection properties. From this identity, we obtain a set of homogeneous linear equations. We then show that this defines the zero subspace of R-/F/. Finally, the desired bound on /F/ is obtained from the bound on the number of linearly independent equations. This proof-technique can also be used to prove a more general theorem (Theorem 2). We conclude by indicating how this technique can be generalised to uniform hypergraphs by proving the uniform Ray-Chaudhuri-Wilson theorem. (C) 1997 Academic Press.